package min_path_one_to_all;

import java.util.*;

public class Path {

 public static void miniPath(List<List<Cell>> list){
	
	 Map<Integer,Integer> map=new HashMap<Integer,Integer>();  
	 int start_num=0;

	 //{0=2, 1=3, 2=4, 3=5, 4=1, 5=3, 6=6, 7=5, 8=6, 9=7, 10=7}
	 while(true){
		 
		int min_node_num=-1;
		int min_node_path=Integer.MAX_VALUE;
		
		for(int i=0;i<list.get(start_num).size();i++){
			    Cell cell=list.get(start_num).get(i);
			if((map.get(cell.getNode())==null)&&(cell.getWeight()<min_node_path)){
				min_node_path=cell.getWeight();
				min_node_num=cell.getNode();
			}	
		} 
		
		Iterator<Integer> it = map.keySet().iterator();		
		while(it.hasNext()){
			int node_num = it.next(); int node_path= map.get(node_num);  
			for(int i=0; i<list.get(node_num).size(); i++){
				Cell cell = list.get(node_num).get(i);
				if(map.get(cell.getNode())==null 
					   && cell.getWeight()+node_path<min_node_path){
					min_node_path=cell.getWeight()+node_path;
					min_node_num=cell.getNode();
				}
			}				
		}
		
		if(min_node_path < Integer.MAX_VALUE){
			map.put(min_node_num,min_node_path);			
		}else{
			break;
		}
	 }
	 System.out.println(map);
   }
}
